/*-------------------------------------------------------------------------
 *
 * knapsack.c
 *	  背包问题求解器
 *
 * 给定输入向量的整数项重量（必须 >= 0）和值（双精度 >= 0），计算产生最大总值的项目集合而不超过指定的总重量；每个项目最多包含一次（这是 0/1 背包问题）。总重量为 0 的项将始终被包括在内。
 *
 * 此算法的性能是伪多项式，O(nW)，其中 W 是重量限制。对于非整数重量或近似解，调用者应将输入重量预缩放到适当的范围。这允许在多项式时间内获得近似解（确切问题的普遍情况是 NP 难的）。
 *
 * Copyright (c) 2017-2022, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *	  src/backend/lib/knapsack.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include <math.h>
#include <limits.h>

#include "lib/knapsack.h"
#include "miscadmin.h"
#include "nodes/bitmapset.h"
#include "utils/builtins.h"
#include "utils/memutils.h"

/*
 * DiscreteKnapsack
 *
 * item_values 输入是可选的；如果省略，假定所有物品的价值为 1。
 *
 * 返回一个 Bitmapset，包含 0..(n-1) 的索引，这些索引是为
 * 包含在解决方案中而选择的物品。
 *
 * 这使用了通常的动态规划算法，调整为在每次迭代中重用
 * 内存（通过从较大重量到较小重量进行处理）。在第 i 次迭代开始时，values[w] 数组包含使用
 * 仅具有索引 < i 的物品计算出的总重量 <= w 的最大值；而 sets[w] 包含实际用于该值的物品的位图。 （所有的
 * bitmapsets 都已预初始化为一个未使用的高位，因此内存
 * 分配只进行一次。）
 */
Bitmapset * DiscreteKnapsack(int fc_max_weight, int fc_num_items,
				 int *fc_item_weights, double *fc_item_values)
{
	MemoryContext fc_local_ctx = AllocSetContextCreate(CurrentMemoryContext,
													"Knapsack",
													ALLOCSET_SMALL_SIZES);
	MemoryContext fc_oldctx = MemoryContextSwitchTo(fc_local_ctx);
	double	   *fc_values;
	Bitmapset **fc_sets;
	Bitmapset  *fc_result;
	int			fc_i,
				fc_j;

	Assert(fc_max_weight >= 0);
	Assert(fc_num_items > 0 && fc_item_weights);

	fc_values = palloc((1 + fc_max_weight) * sizeof(double));
	fc_sets = palloc((1 + fc_max_weight) * sizeof(Bitmapset *));

	for (fc_i = 0; fc_i <= fc_max_weight; ++fc_i)
	{
		fc_values[fc_i] = 0;
		fc_sets[fc_i] = bms_make_singleton(fc_num_items);
	}

	for (fc_i = 0; fc_i < fc_num_items; ++fc_i)
	{
		int			fc_iw = fc_item_weights[fc_i];
		double		fc_iv = fc_item_values ? fc_item_values[fc_i] : 1;

		for (fc_j = fc_max_weight; fc_j >= fc_iw; --fc_j)
		{
			int			fc_ow = fc_j - fc_iw;

			if (fc_values[fc_j] <= fc_values[fc_ow] + fc_iv)
			{
				/* 将 sets[ow] 复制到 sets[j] 而不重新分配 */
				if (fc_j != fc_ow)
				{
					fc_sets[fc_j] = bms_del_members(fc_sets[fc_j], fc_sets[fc_j]);
					fc_sets[fc_j] = bms_add_members(fc_sets[fc_j], fc_sets[fc_ow]);
				}

				fc_sets[fc_j] = bms_add_member(fc_sets[fc_j], fc_i);

				fc_values[fc_j] = fc_values[fc_ow] + fc_iv;
			}
		}
	}

	MemoryContextSwitchTo(fc_oldctx);

	fc_result = bms_del_member(bms_copy(fc_sets[fc_max_weight]), fc_num_items);

	MemoryContextDelete(fc_local_ctx);

	return fc_result;
}
